package com.example.sword;

public class Test25 {

    public static void main(String[] args) {
        System.out.println("haha");
    }

    class Node{
        int val;
        Node next;
        Node random;

        public Node(int val){
            this.val = val;
        }
    }

    /**
     *     输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），
     *     请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
     *
     */

    public Node Clone(Node pHead) {

        if (pHead==null)return null;

        Node currentNode = pHead;

        while (currentNode!=null){
            Node cloneNode = new Node(currentNode.val);
            cloneNode.next = currentNode.next;
            currentNode.next = cloneNode;
            currentNode = cloneNode.next;
        }

        currentNode = pHead;

        while (currentNode!=null){
            if (currentNode.random!=null)
            currentNode.next.random = currentNode.random.next;
            currentNode = currentNode.next.next;
        }

        currentNode = pHead;

        Node cloneHead = currentNode.next;
        while (currentNode!=null){
            Node tempCloneNode = currentNode.next;
            currentNode.next = tempCloneNode.next;
            if (tempCloneNode.next!=null)
            tempCloneNode.next = tempCloneNode.next.next;
            currentNode = currentNode.next;
        }

        return cloneHead;

    }

}
